package problems.solved;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import problems.Problem;
import utils.Pair;
import utils.Utils;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;

public class Problem89 extends Problem<Integer> {
	private static final List<Character> charOrder = ImmutableList.of('I', 'V', 'X', 'L', 'C', 'D', 'M');
	private static final ImmutableMap<Character, Integer> map = ImmutableMap.<Character, Integer> builder()
			.put('I', 1)
			.put('V', 5)
			.put('X', 10)
			.put('L', 50)
			.put('C', 100)
			.put('D', 500)
			.put('M', 1000)
			.build();
	
	ImmutableMap<Character, Pair<Character, Integer>> pairs = ImmutableMap.<Character, Pair<Character, Integer>>builder()
			.put('V', Pair.of('I', 4))
			.put('X', Pair.of('I', 9))
			.put('L', Pair.of('X', 40))
			.put('C', Pair.of('X', 90))
			.put('D', Pair.of('C', 400))
			.put('M', Pair.of('C', 900))
			.build();

	private final List<String> data = new ArrayList<String>();

	public static void main(String[] args) {
		Problem89 problem89 = new Problem89();
		problem89.runTimed();
		problem89.printResult();
	}
	
	@Override
	public void init() {
		Scanner scanner = Utils.getScannerForFile("roman.txt");
		while (scanner.hasNext()) {
			data.add(scanner.nextLine());
		}
	}

	@Override
	public void run() {
		assert data.size() == 1000;
		assert map.keySet().containsAll(charOrder) && charOrder.containsAll(map.keySet());
		
		int result = 0;
		for (String number : data) {
			result += amountSaved(number);
		}
		setResult(result);
	}

	private int amountSaved(String number) {
		int value = valueOf(number);
		assert value > 0 && value < 5000; 
		String minimal = minimalForm(value);
		return number.length() - minimal.length();
	}

	private String minimalForm(int value) {
		int i = charOrder.size()-1;
		StringBuilder minimal = new StringBuilder();
		while (value > 0 && i >= 0) {
			char current = charOrder.get(i);
			
			if (value >= map.get(current)) {
				minimal.append(current);
				value -= map.get(current);
			}
			else if (pairs.containsKey(current)) {
				i--;
				Pair<Character, Integer> pair = pairs.get(current);
				if (value >= pair.getRight()) {
					value -= pair.getRight();
					minimal.append(pair.getLeft()).append(current);
				}
			}
			else {
				i--;
			}
		}
		assert value == 0;
		return minimal.toString();
	}

	private int valueOf(String number) {
		int value = 0;
		for (int i = 0; i < number.length(); i++) {
			char c = number.charAt(i);
			if (i+1 < number.length()) {
				final char nextChar = number.charAt(i+1);
				if (charOrder.indexOf(nextChar) > charOrder.indexOf(c)) {
					value += map.get(nextChar) - map.get(c);
					i++;
					continue;
				}
			}
			value += map.get(c);
		}
		return value;
	}
}
